<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Detecting a small subset of infeasible linear inequalities</title>
<link rel="canonical" href="/Users/mcgrant/Repos/CVX/examples/sparse_heuristics/html/sparse_infeas_dual.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Detecting a small subset of infeasible linear inequalities</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Section 5.8, Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Written for CVX by Almir Mutapcic - 02/18/06</span>
<span class="comment">%</span>
<span class="comment">% We consider a set of linear inequalities A*x &lt;= b which are</span>
<span class="comment">% infeasible. Here A is a matrix in R^(m-by-n) and b belongs</span>
<span class="comment">% to R^m. We apply a l1-norm heuristic to find a small subset</span>
<span class="comment">% of mutually infeasible inequalities from a larger set of</span>
<span class="comment">% infeasible inequalities. The heuristic finds a sparse solution</span>
<span class="comment">% to the alternative inequality system.</span>
<span class="comment">%</span>
<span class="comment">% Original system is A*x &lt;= b and it alternative ineq. system is:</span>
<span class="comment">%</span>
<span class="comment">%   lambda &gt;= 0,   A'*lambda == 0.   b'*lambda &lt; 0</span>
<span class="comment">%</span>
<span class="comment">% where lambda in R^m. We apply the l1-norm heuristic:</span>
<span class="comment">%</span>
<span class="comment">%   minimize   sum( lambda )</span>
<span class="comment">%       s.t.   A'*lambda == 0</span>
<span class="comment">%              b'*lambda == -1</span>
<span class="comment">%              lambda &gt;= 0</span>
<span class="comment">%</span>
<span class="comment">% Positive lambdas gives us a small subset of inequalities from</span>
<span class="comment">% the original set which are mutually inconsistent.</span>

<span class="comment">% problem dimensions (m inequalities in n-dimensional space)</span>
m = 150;
n = 10;

<span class="comment">% fix random number generator so we can repeat the experiment</span>
seed = 0;
randn(<span class="string">'state'</span>,seed);

<span class="comment">% construct infeasible inequalities</span>
A = randn(m,n);
b = randn(m,1);

fprintf(1, [<span class="string">'Starting with an infeasible set of %d inequalities '</span> <span class="keyword">...</span>
            <span class="string">'in %d variables.\n'</span>],m,n);

<span class="comment">% you can verify that the set is infeasible</span>
<span class="comment">% cvx_begin</span>
<span class="comment">%   variable x(n)</span>
<span class="comment">%   A*x &lt;= b;</span>
<span class="comment">% cvx_end</span>

<span class="comment">% solve the l1-norm heuristic problem applied to the alternative system</span>
cvx_begin
   variables <span class="string">lambda(m)</span>
   minimize( sum( lambda ) )
   subject <span class="string">to</span>
     A'*lambda == 0;
     b'*lambda == -1;
     lambda &gt;= 0;
cvx_end

<span class="comment">% report the smaller set of mutually inconsistent inequalities</span>
infeas_set = find( abs(b.*lambda) &gt; sqrt(eps)/n );
disp(<span class="string">' '</span>);
fprintf(1,<span class="string">'Found a smaller set of %d mutually inconsistent inequalities.\n'</span>,<span class="keyword">...</span>
        length(infeas_set));
disp(<span class="string">' '</span>);
disp(<span class="string">'A smaller set of mutually inconsistent inequalities are the ones'</span>);
disp(<span class="string">'with row indices:'</span>), infeas_set'

<span class="comment">% check that this set is infeasible</span>
<span class="comment">% cvx_begin</span>
<span class="comment">%    variable x_infeas(n)</span>
<span class="comment">%    A(infeas_set,:)*x_infeas &lt;= b(infeas_set);</span>
<span class="comment">% cvx_end</span>
</pre>
<a id="output"></a>
<pre class="codeoutput">
Starting with an infeasible set of 150 inequalities in 10 variables.
 
Calling Mosek 9.1.9: 150 variables, 11 equality constraints
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 11              
  Cones                  : 0               
  Scalar variables       : 150             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 11              
  Cones                  : 0               
  Scalar variables       : 150             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 11
Optimizer  - Cones                  : 0
Optimizer  - Scalar variables       : 150               conic                  : 0               
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 66                after factor           : 66              
Factor     - dense dim.             : 0                 flops                  : 2.03e+04        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.4e+01  1.3e+00  3.4e+02  0.00e+00   1.796106379e+02   0.000000000e+00   3.5e+00  0.00  
1   2.7e-01  1.4e-02  3.8e+00  6.32e-01   2.425004055e+00   1.503802157e-02   4.0e-02  0.01  
2   1.1e-01  6.0e-03  1.6e+00  7.03e-01   1.635730887e+00   4.738650042e-01   1.7e-02  0.01  
3   3.5e-02  1.9e-03  5.0e-01  9.39e-01   8.839725117e-01   5.194776806e-01   5.2e-03  0.01  
4   1.1e-02  5.9e-04  1.6e-01  9.42e-01   6.965762866e-01   5.792625116e-01   1.6e-03  0.01  
5   6.4e-03  3.4e-04  9.1e-02  1.01e+00   6.560872319e-01   5.883159430e-01   9.5e-04  0.01  
6   1.4e-03  7.6e-05  2.0e-02  9.93e-01   6.133257838e-01   5.980951257e-01   2.1e-04  0.01  
7   8.4e-05  4.4e-06  1.2e-03  9.98e-01   6.020614393e-01   6.011793223e-01   1.2e-05  0.01  
8   7.6e-08  3.9e-09  1.1e-06  1.00e+00   6.013126376e-01   6.013118411e-01   1.1e-08  0.01  
9   7.6e-12  3.9e-13  1.1e-10  1.00e+00   6.013119804e-01   6.013119803e-01   1.1e-12  0.01  
Basis identification started.
Primal basis identification phase started.
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Optimizer terminated. Time: 0.01    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 6.0131198040e-01    nrm: 1e+00    Viol.  con: 2e-11    var: 0e+00  
  Dual.    obj: 6.0131198032e-01    nrm: 4e+00    Viol.  con: 0e+00    var: 2e-13  

Basic solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 6.0131198034e-01    nrm: 1e+00    Viol.  con: 1e-16    var: 0e+00  
  Dual.    obj: 6.0131198032e-01    nrm: 4e+00    Viol.  con: 0e+00    var: 4e-16  
Optimizer summary
  Optimizer                 -                        time: 0.01    
    Interior-point          - iterations : 9         time: 0.01    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.601312
 
 
Found a smaller set of 11 mutually inconsistent inequalities.
 
A smaller set of mutually inconsistent inequalities are the ones
with row indices:

ans =

     1    22    33    54    59    73    79    94   115   136   149

</pre>
</div>
</body>
</html>